原始题目:剑指 Offer 07. 重建二叉树 (opens new window)
解题思路:
先序遍历性质:节点按照 【根节点 | 左子树 | 右子树】排序。
中序遍历性质:节点按照 【左子树 | 根节点 | 右子树】排序。
根据以上性质,有以下结论:
先序遍历的首个元素 为根节点的值。
在中序遍历中的位置,可以将中序遍历数组划分为左子树部分和右子树部分。
根据结论 ,可以计算左子树的节点数,因此可以再将先序遍历划分为左子树部分和右子树部分。
根据以上结论,可以使用递归的方式对所有子树进行划分。
递归函数
递归参数:先序遍历数组 ,先序遍历的区间 , ;中序遍历数组 ,中序遍历的区间 ,。
终止条件: 或者 。
递推工作:
- 根据 和 ,可以得到根节点的值 ,通过 拿到其在 中的位置 ,所以 中,左子树的区间为 ,右子树的区间为 。
- 将 划分左右子树部分。左子树的个数应该为 ,所以 中左子树的区间为 ,右子树的区间为 。
- 创建根节点,根据 、 步得到的左右子树区间,继续进行递归,将根节点的左右孩子指向递归函数的返回值。
代码:
public TreeNode buildTree(int[] preorder, int[] inorder) {
if(preorder == null || inorder == null
|| preorder.length == 0 || preorder.length != inorder.length){
return null;
}
return buildTree(
preorder, 0, preorder.length - 1,
inorder, 0, inorder.length - 1);
}
private TreeNode buildTree(int[] preOrder, int preStart, int preEnd,
int[] inOrder, int inStart, int inEnd) {
if (preStart > preEnd || inStart > inEnd) {
return null;
}
int rootVal = preOrder[preStart];
int rootIdxInOrder = findIndex(inOrder, inStart, inEnd, rootVal);
TreeNode root = new TreeNode(rootVal);
// 如何确定 preEnd 的大小?
// 通过 rootIdxInOrder 其实可以确定 preOrder 中,那部分是属于左子树的
// 左子树的节点个数为 rootIdxInOrder - inStart,preEnd 应该 preStart + rootIdxInOrder - inStart
int newPreEnd = preStart + rootIdxInOrder - inStart;
root.left = buildTree(preOrder, preStart + 1, newPreEnd, inOrder, inStart, rootIdxInOrder - 1);
root.right = buildTree(preOrder, newPreEnd+1, preEnd, inOrder, rootIdxInOrder + 1, inEnd);
return root;
}
/**
* 拿到根节点在中序遍历数组中的索引位置
*/
private int findIndex(int[] inOrder, int s, int e, int root) {
for (int i = s; i <= e; i++) {
if (inOrder[i] == root) {
return i;
}
}
return -1;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
复杂度分析
时间复杂度 :递归共建立 个节点,每层递归中的节点建立占用 ,寻找根节点位置的循环总共占用,因此使用 时间。
空间复杂度 :最差情况下,树是一个链表,需要占用函数栈的空间为 。当树为满二叉树时,递归深度为 ,占用 的空间。